In general, for mathematical processing, a route network, in particular a road network, may be represented by a route search algorithm as a graph having segments and nodes. The segments represent the roads, and the nodes represent mesh points in the road network.
(Travel) resistances may be associated with the segments and/or nodes, the resistances being represented in the form of a travel segment or a travel time. When resistances, namely the segment resistances or path resistances, are associated with the segments in this context, the segment resistance or path resistance represents a measured variable for the expenditure to travel from one node to another in the road network. When resistances, namely the node resistances, are additionally or alternatively associated with the nodes, a resistance, or more precisely, the node resistance, is described in the node for every conceivable combination of an arriving segment and a departing segment.
In the simplest case, the segment lengths may be used as the path resistance. Alternatively, the travel time may be based on a segment as the path resistance, or the path resistance may be determined by a function in which the travel time, the path resistance, and/or other variables are entered on a weighted basis.
All conventional “best path” algorithms ultimately specify a route between a starting segment and a destination segment in directed graphs having the characteristic that the sum of all the resistances associated with the segments and/or the nodes has a minimum.
The route is described by a series of segments, and the remaining travel time, remaining route distance, and resistance remaining at the destination point being specified (in other words, if the segment length is selected as the path resistance, a search is made for the shortest route in the graph).
Based on this method, known from European Published Patent Application No. 979 987, for example, for determining a route from a starting point to a destination point on a route network, in particular a road network, navigation systems are currently able to dynamize the guidance of a means of transportation, in particular a motor vehicle, so that traffic messages triggered by a traffic-related event on the route to the destination, such as blockage, congestion, or stop-and-go traffic, and/or a traffic accident, for example, are detected and the navigation system automatically calculates a detour alternative to the original route, i.e., the route defined before the traffic message was taken into account.
In this context, traffic messages are represented in graphs by an increase in the path resistance of the affected segments; alternatively or additionally, it is also possible to represent the increase in resistance in the nodes. In addition to the increase in path resistances and/or node resistances, in principle an “avoidance” or “prohibition” of certain segments affected by a traffic message and/or certain nodes affected by a traffic message may be implemented; such a “prohibition” is algorithmically converted in such a way that this prohibition is equivalent to an absence of the corresponding segment and/or corresponding node, which is equated with the association of an infinite path resistance with the affected segment, and/or an infinite node resistance with the affected node.
Possible providers or suppliers of such traffic messages include external sources, for example radio transmitters which transmit coded traffic messages via their TMC (Traffic Message Channel, which is a channel for traffic broadcasts, i.e., a traffic radio channel which automatically detects traffic situations and provides appropriate traffic messages) in the RDS (Radio Data System)/TMC standard, or service providers which transmit traffic messages using the SMS (Short Message Service) of the GSM (Global System for Mobile Communication) network.
In such traffic messages from external sources, deletion is performed either by the radio transmitter providing separate deletion messages, or by the transmitter providing the traffic message with a period of validity immediately upon transmission to the navigation system, or the navigation system providing the traffic message with a separate period of validity; in each case the route must always be recalculated when traffic messages are deleted from external sources so that the navigation system is able to check whether the route could change again due to the absence of a blockage.
On the other hand, the driver him/herself (in the following: the driver) in comes into consideration as an internal source by manually defining a traffic-related event such as blockage, congestion, or stop-and-go traffic and/or a traffic accident on one or more segments of the route via an MMI (man-machine interface), and then allowing the navigation system to determine a detour alternative, i.e., a new route which bypasses the manual blockage. If the driver has reached the destination, the manual blockage may be automatically deleted from the navigation system.
The driver also may actuate the deletion of the manual blockage at any time via a suitable command in the MMI. After this driver-initiated deletion of blockages, however, the navigation system must always recalculate the route so that the navigation system is able to check whether the route could change again due to the absence of a blockage.
The existence of a particular problem in the criterion for automatic deletion of traffic messages may be illustrated by the fact that when the traffic message is deleted too soon the route disadvantageously reverts to the traffic segment to be avoided, and the driver is thus led once again through the triggering event for the traffic message, i.e., the blockage, congestion, or stop-and-go traffic and/or the traffic accident. (For example, the driver defines a segment when a route is present and blocks this segment manually; the navigation system determines a new alternative route which bypasses the manual blockage by the driver and which the driver follows; if the blockage is now deleted too soon from the navigation system, the new route inadvertently leads once more through the blocked segment of the route which was originally selected.)
In contrast, if the navigation system deletes the traffic messages too late (in the extreme case, as described above according to the related art, not until the destination is reached), valuable memory resources in the navigation system remain occupied too long by traffic messages which are of no value and irrelevant to the continuing route. (For example, assume a route from Hamburg to Munich for which the driver, in order to bypass a local construction site in the Hamburg city center, defines a blockage on this segment of the route, but this blockage is not deleted by the navigation system until several hours later when the destination in Munich is reached; if the driver is provided with, for example, a list of the deletions of individual blockages, or merely with a list of current blockages, a blockage in Hamburg is rather confusing if the driver is already in Munich.)
If it is left up to the driver to delete superfluous traffic messages because they are no longer relevant to the route, this is not conducive to road safety since the driver must concentrate on the navigation system. In addition, the navigation system must always recalculate the route, so that the driver is without guidance instructions during the recalculation.